package com.skh.stack;

/**
 * @Author: skh
 * @Date: 2019/6/14 14:07
 * @Description: 1021. 删除最外层的括号
 */
public class RemoveOuterParentheses {

    /*
    有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

    如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

    给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

    对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

    示例 1：

    输入："(()())(())"
    输出："()()()"
    解释：
    输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
    删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
    示例 2：

    输入："(()())(())(()(()))"
    输出："()()()()(())"
    解释：
    输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
    删除每隔部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
    示例 3：

    输入："()()"
    输出：""
    解释：
    输入字符串为 "()()"，原语化分解得到 "()" + "()"，
    删除每个部分中的最外层括号后得到 "" + "" = ""。
     */

    /*
    模拟栈的过程 （ ->flag ++   ）-> flag--

    当flag等于0 之后我们就会得到一个独立的部分 ， 然后再把首尾两个括号去掉 即可
     */
    public String removeOuterParentheses(String S) {

        char[] chars = S.toCharArray();
        StringBuilder sb = new StringBuilder();
        int count = 0;
        String s = "";

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                count++;
                s += chars[i];
            }else {
                count--;
                s+=chars[i];
            }

            if (count == 0) {
                sb.append(s, 1, s.length() - 1);
                s = "";
            }

        }
        return sb.toString();
    }

    public static void main(String[] args) {
        RemoveOuterParentheses removeOuterParentheses = new RemoveOuterParentheses();
        String s = removeOuterParentheses.removeOuterParentheses("()()");
        System.out.println("s = " + s);
    }

}
